//heap.cc
//  Define the internal workings of the ThreadHeap class. Always pop's a thread
//  with the minimum priority.
#include "scheduler.h"
#include "system.h"

#define START_SIZE 16

//Allocate space for the new heap.
ThreadHeap::ThreadHeap() {
    //Note that heap[0] is ignored to make array accesses simpler.
    heap = new Thread*[START_SIZE];
    size = 0;
    storage = START_SIZE;
}

//Deallocate memory dynamically associated with the ThreadHeap class.
ThreadHeap::~ThreadHeap() {
    delete heap;
}

//If there are any threads in the heap, pop one, and put it on the scheduler's
//ready queue.
void
ThreadHeap::readyOne() {
    Thread* thread = pop();
    if(NULL != thread) {
        scheduler->ReadyToRun(thread);
    }
}

//Determine if the queue is empty.
//  @returns true if the queue contians no elements.
bool
ThreadHeap::isEmpty() {
    return size == 0;
}

//Push an element onto the heap.
//  @param thread the thread to be added.
void
ThreadHeap::push(Thread* thread) {
    int insert = size + 1;

    ASSERT(NULL != thread);

    //If the capacity of the heap array has been met, grow it.
    if(size == storage - 1) {
        grow();
    }

    //Insert the new element into the heap.
    heap[insert] = thread;

    //Ensure that the new element is shifted up if it has a higher priority
    //than its parents. Favor keeping the new element on the bottom right of
    //the heap. Leave older elements on the top.
    while(insert > 1 && leftLess(heap[insert/2], heap[insert])) {
        Thread* temp = heap[insert];
        heap[insert] = heap[insert/2];
        heap[insert/2] = temp;
        insert /= 2;
    }

    size++;
}

//Pop an element off the heap.
//  @returns an element with the highest priority in the heap.
Thread*
ThreadHeap::pop() {
    Thread* rtn = heap[1];

    //Return null if the heap is empty.
    //Also, if the heap was grown at any point before, shrink it to the
    //original size.
    if(size == 0) {
        if(storage > START_SIZE) {
            delete heap;
            heap = new Thread*[START_SIZE];
        }
        return NULL;
    }

    //Put the last added item on the head of the heap.
    heap[1] = heap[size--];

    //When shifting the pivot down the heap, favor pushing it down the heap,
    //and pushing it to the right. This favors putting the element back where
    //it came from, and tries to keep threads that have been waiting the
    //longest on top of the heap. Starvation can still occur, since it is
    //harder for threads on the left to move up the heap.

    //While pivot has at least a left child.
    for(int pivot = 1; pivot * 2 < size; ) {
        int left = pivot * 2;
        int right = left + 1;

        //If a right child exists, and has at least the same priority
        //as the left child. (Bias it to the right side of the heap)
        if(right <= size && !leftLess(heap[right], heap[left])) {
            //And the right child has an equal or higher priority than the
            //pivot, swap the pivot and it's right child.
            if(!leftLess(heap[right], heap[pivot])) {
                Thread* tmp = heap[pivot];
                heap[pivot] = heap[right];
                heap[right] = tmp;

                pivot = right;
                continue;
            }
            //Left child exists, and has a greater priority than the right child of
            //the pivot.
        } else {

            if(!leftLess(heap[left], heap[pivot])) {
                //Swap the pivot and its left child.
                Thread* tmp = heap[pivot];
                heap[pivot] = heap[left];
                heap[left] = tmp;

                pivot = left;
                continue;
            }
        }
        break;
    }
    return rtn;
}

//Determine if the first Thread* argument has lower priority than the second
//argument.
bool
ThreadHeap::leftLess(Thread* left, Thread* right) {
    return left->getPriority() < right->getPriority();
}

//Print the contents of the heap.
void
ThreadHeap::print() {
    for(int i = 0; i < size; i++) {
        heap[i]->Print();
    }
}

//Increase the size of the heap array.
void
ThreadHeap::grow() {
    Thread** newHeap = new Thread*[storage*2];
    for(int i = 1; i < storage; i++) {
        newHeap[i] = heap[i];
    }

    delete heap;
    heap = newHeap;
}
